1768E - Partial Sorting - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const int MN=1e7+10;
int MOD=1e9+7;
const int bits=31;
using pi = pair<ll, ll>;
using ti = tuple<ll, ll, ll>;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define MAX_SIZE 1000005
#define lcm(a, b) (a*b)/__gcd(a, b)

int norm(int x) {
    if (x < 0) {
        x += MOD;
    }
    if (x >= MOD) {
        x -= MOD;
    }
    return x;
}

template<class T>
T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}


struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(MOD - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, MOD - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = ll(x) * rhs.x % MOD;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, m; cin>>n>>m;
    MOD=m;

    vector<Z> fac(MN), iFac(MN), pow2(MN);
    
    fac[0] = pow2[0] = 1;
    for (int i = 1; i < MN; i++) {
        fac[i] = i * fac[i - 1];
        pow2[i] = 2 * pow2[i - 1];
    }
    iFac[MN - 1] = fac[MN - 1].inv();
    for (int i = MN - 1; i; i--) {
        iFac[i - 1] = i * iFac[i];
    }

    auto C = [&](int i, int j) {
        if (i<0 || j<0 || i<j){
            return (Z)0;
        }
        return fac[i] * iFac[j] * iFac[i - j];
    };

    auto P = [&](int i, int j) {
        return fac[i] * iFac[i - j];
    };

    // total
    Z ans=fac[3*n];
    ans*=3;

    // 2 operations
    Z sub=fac[2*n];
    sub*=2; sub-=fac[n];
    ans-=sub;

    // 0 operations
    ans-=1;

    // 1 operation
    // fix middle n elements that we choose
    Z sub2=C(2*n, n); sub2*=fac[2*n]; sub2*=fac[n]; sub2*=2;

    for (int i=0; i<=n; i++){
        Z take=C(n, i); take*=C(n, n-i);
        take*=C(2*n-i, n);
        take*=fac[n]; take*=fac[n]; take*=fac[n];
        sub2-=take;
    }

    ans-=sub2;

    cout<<ans.x<<endl;










}